home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cpp_libs
/
cool
/
ge_cool.lha
/
GE_COOL2.1
/
src
/
Tree
/
N_Node.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-05-15
|
7KB
|
196 lines
//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
#include <cool/N_Node.h>
// CoolN_Node -- Simple constructor that allocates enough storage for a vector of
// pointers to CoolN_Node objects
// Input: None
// Output: None
template <class Type, int nchild>
CoolN_Node<Type,nchild>::CoolN_Node<Type,nchild> () {
for (int i = 0; i < nchild; i++) // For each pointer in vector
this->sub_trees[i] = NULL; // Insure NULL pointer value
if (this->compare_s == NULL) // If no compare function
this->compare_s = &Type##_default_CoolN_Node_compare; // Default
}
// CoolN_Node -- Simple constructor that allocates enough storage for a vector of
// pointers to CoolN_Node objects and assigns an initial data value
// Input: Data slot value
// Output: None
template <class Type, int nchild>
CoolN_Node<Type,nchild>::CoolN_Node<Type,nchild> (const Type& value) {
this->data = value; // Copy initial data value
for (int i = 0; i < nchild; i++) // For each pointer in vector
this->sub_trees[i] = NULL; // Insure NULL pointer value
if (this->compare_s == NULL) // If no compare function
this->compare_s = &Type##_default_CoolN_Node_compare; // Default
}
// CoolN_Node -- Copy constructor makes deep copy
// Input: Reference to CoolN_Node
// Output: None
template <class Type, int nchild>
CoolN_Node<Type,nchild>::CoolN_Node<Type,nchild> (const CoolN_Node<Type,nchild>& n) {
for (int i = 0; i < nchild; i++) // For each pointer in vector
this->sub_trees[i] = copy_nodes(n.sub_trees[i]); // Deep copy of subnodes
this->data = n.data; // Copy data value
this->compare_s = n.compare_s; // Set compare method
}
// ~CoolN_Node -- Destructor for the CoolN_Node<Type,nchild> class
// Input: None
// Output: None
template <class Type, int nchild>
CoolN_Node<Type,nchild>::~CoolN_Node<Type,nchild> () {
for (int i = 0; i < nchild; i++) // For each pointer in vector
delete this->sub_trees[i]; // Invoke destructor
}
// is_leaf -- Determine if node has any children
// Input: None
// Output: TRUE if no children, else FALSE
template <class Type, int nchild>
Boolean CoolN_Node<Type,nchild>::is_leaf () const {
for (int i = 0; i < nchild; i++)
if (this->sub_trees[i])
return (FALSE);
return TRUE;
}
// operator[] -- Overload the brackets operator to provide a mechanism to set
// and/or get a sub-tree pointer of a node whose zero-relative
// index is specified from left to right
// Input: Zero-relative index into vector of sub-tree pointers
// Output: Reference to a pointer value
template <class Type, int nchild>
inline CoolN_Node_##Type##_##nchild##_p& CoolN_Node<Type,nchild>::operator[] (int index) {
#if ERROR_CHECKING
if (index >= nchild) // If index out of range
this->index_error ("operator[]", index); // Raise exception
#endif
return (this->sub_trees[index]);
}
// operator= -- Overload the assignment operator to copy all values from one
// node object to another. This routine could potentially result
// in a complete deep copy, since for each valid sub_tree pointer,
// a new node is allocated and its sub_tree pointers copied.
// Input: Reference to CoolN_Node
// Output: Rererence to updated CoolN_Node
template <class Type, int nchild>
CoolN_Node<Type,nchild>& CoolN_Node<Type,nchild>::operator= (const CoolN_Node<Type,nchild>& n) {
for (int i = 0; i < nchild; i++) { // Invoke destructor recursively
delete this->sub_trees[i]; // for all subnodes
this->sub_trees[i] = copy_nodes(n.sub_trees[i]); // and make new deep copy
}
this->data = n.data; // Copy data value
return *this; // Return reference
}
// insert_before -- Insert sub-tree pointer to child before the specified
// zero-relative sub-tree index (numbered from left to right)
// Input: Pointer to child node, zero-relative index
// Output: TRUE/FALSE
template <class Type, int nchild>
Boolean CoolN_Node<Type,nchild>::insert_before (CoolN_Node<Type,nchild>& n, int index) {
#if ERROR_CHECKING
if (index < 0 || index >= nchild) { // If index out of range
this->index_error ("insert_before", index); // Raise exception
return FALSE; // Return failure status
}
#endif
for (int i = nchild-1; i > index; i--) // For each pointer after index
this->sub_trees[i] = this->sub_trees[i-1]; // Move up one in vector
this->sub_trees[i] = &n; // Pointer to new sub-tree
return TRUE; // Return success status
}
// insert_after -- Insert sub-tree pointer to child after the specified
// zero-relative sub-tree index (numbered from left to right)
// Input: Pointer to child node, zero-relative index
// Output: TRUE/FALSE
template <class Type, int nchild>
Boolean CoolN_Node<Type,nchild>::insert_after (CoolN_Node<Type,nchild>& n, int index) {
#if ERROR_CHECKING
if (index < 0 || index >= nchild) { // If index out of range
this->index_error ("insert_after", index); // Raise exception
return FALSE; // Return failure status
}
#endif
for (int i = nchild-1; i > index+1; i--) // For each pointer after index
this->sub_trees[i] = this->sub_trees[i-1]; // Move up one in vector
this->sub_trees[i] = &n; // Pointer to new sub-tree
return TRUE; // Return success status
}
// copy_nodes -- Copies this node and all its subnodes
// Input: pointer to node to be copied
// Output: pointer to new copy of node with all new subnodes.
template <class Type, int nchild>
CoolN_Node<Type,nchild>* CoolN_Node<Type,nchild>::copy_nodes (const CoolN_Node<Type,nchild>* n) const {
if (n == NULL)
return NULL;
CoolN_Node<Type,nchild>* new_n = new CoolN_Node<Type,nchild>;
for (int i = 0; i < nchild; i++) // For each pointer in vector
new_n->sub_trees[i] = copy_nodes(n->sub_trees[i]); // Deep copy of subnodes
new_n->data = n->data; // Copy data value
return new_n; // Return copied node.
}
// index_error -- Raise exception invalid index
// Input: Function name, invalid index
// Output: None
template <class Type, int nchild>
void CoolN_Node<Type,nchild>::index_error (const char* fcn, int n) {
//RAISE Error, SYM(CoolN_Node), SYM(Out_Of_Range),
printf ("CoolN_Node<%s,%d>::%s: Index %d out of range.\n", #Type, nchild,
fcn, n);
abort ();
}
// default_CoolN_Node_compare -- Default node comparison function utilizing builtin
// less than, equal, and greater than operators
// Input: Reference to two Type data values
// Output: -1, 0, or 1 if less than, equal to, or greater than
template <class Type, int nchild> CoolN_Node {
int Type##_default_CoolN_Node_compare (const Type& v1, const Type& v2) {
if (v1 == v2) // If data items equal
return 0; // Return zero
if (v1 < v2) // If this less than data
return -1; // Return negative one
return 1; // Else return positive one
}
}